package com.example.demo.MyTest.Tree;

import java.util.*;

/**
 * @description:
 * @author: yyc
 * @time: 2021/11/25 21:27
 */
public class SolutionFormer {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode();
        treeNode.val = 1;
        TreeNode left = new TreeNode();
        left.val = 2;
        treeNode.left = left;
        TreeNode ll = new TreeNode();
        ll.val=3;
        treeNode.left.left = ll;
        TreeNode lR = new TreeNode();
        lR.val = 4;
        treeNode.left.right = lR;

        TreeNode right= new TreeNode();
        right.val = 5;
        treeNode.right = right;

        TreeNode Rl = new TreeNode();
        Rl.val=6;
        treeNode.right.left = Rl;
        TreeNode RR = new TreeNode();
        RR.val = 7;
        treeNode.right.right = RR;

//        former(treeNode);
//        former2(treeNode);
//        mid(treeNode);
        after(treeNode);

    }

    /**
     * 前序遍历 - 迭代法
     */
    private static List<Integer> former(TreeNode root){

        //模拟栈
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        while(!stack.isEmpty() || root!=null){
            //递归入栈
            while(root!=null){
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }
            //递归到子节点左节点为Null，出栈
            root = stack.pop();
            root = root.right;
        }

        return list;
    }

    /**
     * 前序遍历另一种解法
     * @param root
     * @return
     */
    private static List<Integer> former2(TreeNode root){
        if(root == null){
            return new ArrayList<>();
        }
        //根-左-右， 因此右子树先入栈
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        stack.push(root);
        while (!stack.isEmpty()){
            list.add(root.val);
            if(root.right!=null){
                stack.push(root.right);
            }
            if(root.left!=null){
                stack.push(root.left);
            }
            root = stack.pop();
        }
        return list;
    }

    /**
     * 中序遍历
     * @param root
     * @return
     */
    private static List<Integer> mid(TreeNode root){
        //模拟栈
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        while(!stack.isEmpty() || root!=null){
            //递归左子树
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            //左子树节点为null时，加入结果集
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }

        return list;
    }

    /**
     * 后序遍历
     * @param root
     * @return
     */
    private static List<Integer> after(TreeNode root){
        //模拟栈 左 - 右 - 根
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        //维护一个TreeNode指针指向上一个被加入结果集的节点
        TreeNode prev = null;
        while(!stack.isEmpty() || root!=null){
            //递归左子树
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            //当前节点的右子树若不为空且未被遍历过，则进入
            if(root.right!=null && root.right != prev){
                //当前节点入栈
                stack.push(root);
                //进入右节点
                root = root.right;
            }else{
                //加入结果集
                list.add(root.val);
                //更新prev指针
                prev = root;
                root = null;
            }
        }

        return list;
    }


    private static List<Integer> preorderTraversal(TreeNode root){
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.isEmpty()){
            TreeNode node = st.peek();
            if(node==null){
                //遇到空节点
                st.pop();
                node = st.peek();
                //下一个节点放入结果集
                st.pop();
                result.add(node.val);
            }else{
                //节点不为空
                st.pop();
                if(node.right!=null){
                    st.push(node.right);
                }
                if(node.left!=null){
                    st.push(node.left);
                }
                st.push(node);
                st.push(null);
            }
        }

        return result;
    }

}
